package com.github.kilianB.pcg.cas;

import java.util.concurrent.atomic.AtomicLong;

import com.github.kilianB.pcg.Pcg;
import com.github.kilianB.pcg.RandomBase64;

/**
 * Base class for 64 bit state pcg random number generators.
 * 
 * The PCG family uses a linear congruential generator as the state-transition
 * function—the “CG” of PCG stands for “congruential generator”. Linear
 * congruential generators are known to be statistically weak.
 * <p>
 * 
 * PCG uses a new technique called permutation functions on tuples to produce
 * output that is much more random than the RNG's internal state. The output
 * function is defined by the extending classes.
 * 
 * A paper highlighting the individual properties can be found here. <a href=
 * "http://www.pcg-random.org/paper.html">http://www.pcg-random.org/paper.html</a>.
 * This class is an adaption to the original c
 * <a href="https://github.com/imneme/pcg-c">source code</a> provided by M.E.
 * O'Neill.
 * 
 * <b>Contract:</b> every extending class <b>must</b> implement the
 * (long,long,boolean) constructor and pass it's argument to the superclass.
 * This constructor functions as copy constructor and blindly passes the
 * arguments on. As it does not perform proper initialization of the seed this
 * method should not be exposed.
 * 
 * @author Kilian
 *
 * @see <a href="http://www.pcg-random.org/">www.pcg-random.org</a>
 */
public abstract class RandomBaseCAS extends RandomBase64 implements Pcg {

	private static final long serialVersionUID = -4396858403047759432L;

	/**
	 * linear congruential constant. Same as MMIX by Donald Knuth and Newlib, Musl
	 */
	protected long mult64 = 6364136223846793005L;

	/** 64 bit internal state */
	protected AtomicLong state;

	/** Stream number of the rng. */
	protected long inc;

	/**
	 * Seeds the generator with 2 longs generated by xorshift*. The values choosen
	 * are very likely not used in any other invocation of this constructor.
	 */
	public RandomBaseCAS() {
		super();
	}

	/**
	 * Create a random number generator with the given seed and stream number. The
	 * seed defines the current state in which the rng is in and corresponds to
	 * seeds usually found in other RNG implementations. RNGs with different seeds
	 * are able to catch up after they exhaust their period and produce the same
	 * numbers.
	 * <p>
	 * 
	 * Different stream numbers alter the increment of the rng and ensure distinct
	 * state sequences
	 * <p>
	 * 
	 * Only generators with the same seed AND stream numbers will produce identical
	 * values
	 * <p>
	 * 
	 * @param seed         used to compute the starting state of the RNG
	 * @param streamNumber used to compute the increment for the lcg.
	 */
	public RandomBaseCAS(long seed, long streamNumber) {
		state = new AtomicLong(0);
		// We need to ensure
		inc = (streamNumber << 1) | 1; // 2* + 1
		stepRight();
		// Won't be contested in the constructor
		state.addAndGet(seed);
		stepRight();
	}

	/**
	 * Copy constructor. <b>Has</b> to be implemented in all inheriting instances.
	 * This will be invoked through reflection!. If no special behavior is desired
	 * simply pass though the values.
	 * 
	 * @param initialState of the lcg
	 * @param increment    used in the lcg. has to be odd
	 * @param dummy        used to resolve signature disambiguate
	 */
	@Deprecated
	protected RandomBaseCAS(long initialState, long increment, boolean dummy) {

		if (increment == 0) {
			throw new IllegalArgumentException("The increment can't be 0");
		}

		if (increment % 2 == 0) {
			throw new IllegalArgumentException("Increment has to be odd");
		}

		// Use getters and setters to let fast implementation overwrite this behavior
		// while still
		// maintaining inheritance.
		setState(initialState);
		setInc(increment);
	}

	/**
	 * Update the state of the lcg and move a step forward. The old state should be
	 * used to extract bits used to construct a number.
	 *
	 * @return the old value of the state variable before updating.
	 */
	protected long stepRight() {
		long oldState;
		long newState;
		// CAS -> thread safety good for low congestion
		final AtomicLong state = this.state;
		do {
			oldState = state.get();
			newState = (oldState * mult64) + inc;
			// System.out.println("CasLoop: State" + state + " Cur Inc" + inc + " Old value:
			// " + oldState + " NewState:" + newState );
		} while (!state.compareAndSet(oldState, newState));

		return oldState;
	}

	/**
	 * Advance or set back the rngs state.
	 * 
	 * In other words fast skip the next n generated random numbers or set the PNG
	 * back so it will create the last n numbers in the same sequence again.
	 * 
	 * <pre>
	 * 	int x = nextInt();
	 * 	nextInt(); nextInt();
	 * 	step(-3);
	 *	int y = nextInt(); 
	 *	x == y TRUE
	 * </pre>
	 * 
	 * Be aware that this relationship is only true for deterministic generation
	 * calls. {@link #nextGaussian()} or any bound limited number generations might
	 * loop and consume more than one step to generate a number.
	 * <p>
	 * 
	 * To advance n steps the function performs <code>Math.ceil( log2(n) )</code>
	 * iterations. So you may go ahead and skip as many steps as you like without
	 * any performance implications.
	 * <p>
	 * 
	 * Negative indices can be used to jump backwards in time going the long way
	 * around
	 * 
	 * 
	 * @param steps the amount of steps to advance or in case of a negative number
	 *              go back in history
	 * 
	 */
	public void advance(long steps) {

		long acc_mult = 1;
		long acc_plus = 0;

		long cur_plus = inc;
		long cur_mult = mult64;

		while (Long.compareUnsigned(steps, 0) > 0) {
			if ((steps & 1) == 1) { // Last significant bit is 1
				acc_mult *= cur_mult;
				acc_plus = acc_plus * cur_mult + cur_plus;
			}
			cur_plus *= (cur_mult + 1);
			cur_mult *= cur_mult;
			steps = Long.divideUnsigned(steps, 2);
		}
		// CAS
		long oldState;
		long newState;
		final AtomicLong state = this.state;
		do {
			oldState = state.get();
			newState = (acc_mult * oldState) + acc_plus;
		} while (!state.compareAndSet(oldState, newState));
	}

	/**
	 * Construct a 32bit int from the given 64bit state using a permutation
	 * function. The produced int will be used to construct all other datatypes
	 * returned by this RNG.
	 * 
	 * @param state random int as produced by the internal lcg
	 * @return a random int
	 * 
	 */
	protected abstract int getInt(long state);

	/**
	 * Return true if this rng is a fast instance. This check is mostly used int he
	 * distance calculation due to the fact that the state of fast RNGs is shifted
	 * by one. They first calculate a new value and directly use it instead of using
	 * the old state and calculating a new one
	 * 
	 * @return true if the subclass uses the newly generated state directly
	 */
	public boolean isFast() {
		return false;
	}

	public long getState() {
		return state.get();
	}

	public long getInc() {
		return inc;
	}

	protected void setInc(long increment) {
		if (increment == 0 || increment % 2 == 0) {
			throw new IllegalArgumentException("Increment may not be 0 or even. Value: " + increment);
		}
		this.inc = increment;
	}

	protected void setState(long initialState) {
		// Do we need to CAS it?
		if (this.state == null) {
			this.state = new AtomicLong(initialState);
		}
		this.state.set(initialState);
	}
}
